//
// Created by isabella on 25-5-25.
//
#include <common.h>

class RandomizedSet {
private:
    vector<int> data;
    unordered_map<int, int> map;

public:
    RandomizedSet() {
        srand(time(NULL));
    }

    bool insert(int val) {
        if(map.contains(val)) {
            return false;
        }
        data.push_back(val);
        map[val]=data.size()-1;
        return true;
    }

    bool remove(int val) {
        if(!map.contains(val)) {
            return false;
        }
        int idx = map[val];
        int last = data.back();
        data[idx]=last;
        data.pop_back();

        map[last]=idx;
        map.erase(val);

        return true;
    }

    int getRandom() {
        int idx = rand()%data.size();
        return data[idx];
    }
};

int main() {
    auto objp = new RandomizedSet();
    objp->remove(0);
    objp->remove(0);
    objp->insert(0);
    int random = objp->getRandom();
    cout << random << endl;
    objp->remove(0);
    objp->insert(0);
    delete objp;
    return 0;
}
